import datastructure.linklist.ListNode;

import java.util.PriorityQueue;

/**
 * @Author ZhangCuirong
 * @Date 2025/8/4 20:11
 * @description:
 */
public class Solution23 {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode dummy = new ListNode(-1);
        if (lists.length == 0) {
            return null;
        }
        PriorityQueue<ListNode> queue = new PriorityQueue<>((k1, k2) -> k1.val - k2.val);
        for (int i = 0; i < lists.length; i++) {
            if(lists[i]!=null){
                queue.add(lists[i]);
            }
        }
        ListNode cur = dummy;
        while (!queue.isEmpty()) {
            ListNode p = queue.poll();
            cur.next = p;
            cur = cur.next;
            if (p.next != null) {
                queue.add(p.next);
            }
        }
        return dummy.next;
    }

    public static void main(String[] args) {
        ListNode p1 = ListNode.arrayToList(new int[]{1, 4, 5});
        ListNode p2 = ListNode.arrayToList(new int[]{1, 3, 4});
        ListNode p3 = ListNode.arrayToList(new int[]{2, 6});
        ListNode[] lists = {p1, p2, p3};
        Solution23 solution = new Solution23();
        ListNode head = solution.mergeKLists(lists);
        ListNode.printList(head);

    }
}
